Software of the Month Club 1997 January

home *** CD-ROM | disk | FTP | other *** search

/ Software of the Month Club 1997 January / Software of the Month Club 1997 January.iso / pc / dos / child / velena / connect4.doc next >

Wrap

Text File | 1996-11-16 | 26.2 KB | 636 lines

-+- Velena -+- A Connect Four Expert System which Plays the Game Perfectly =========================================================== Abstract ======== Velena is a Shannon-C type strategy program written to play Connect Four. It's based on a knowledged approach that uses eight mathematical rules to take its decisions. Since the rules are proven to be correct, the conclusions made by the program are also correct. In this way it has been possible to show that Connect Four is a first player win and Velena is always able to win when she plays first. =============================================================================== 1. Program overview =================== 1.1. System Requirements ======================== To run Velena, you will need the following system: * An IBM compatible, 386 or better computer (486/DX2 suggested) * Four megabytes of RAM. * A SVGA VESA-compatible graphic adapter. * MS-DOS 5.0 (or better) or compatible operating system. 1.2. Freeware agreement ======================= This program is to be considered freeware, which means that you can use and distribute it to anyone you want, provided no fee is charged except for media support. You should also not disassemble modify or reverse engineer the program for any reason in any circumstance. The program is offered as is without warrants of any kind, even if the best efforts have been made to produce a functional and efficient product. I should not be liable for any damage caused by the use or misuse of this program. Running the program is entirely at user's risk. Even if a fee is not required, I will be glad to receive a postcard from your hometown with your comments and suggestion about my program. The author current address is: Giuliano Bertoletti Via Bocchialini n.6 Cap. 43100, Parma. Italy E-Mail: gbe@aida.eng.unipr.it Fidonet: 2:332/801.6 1.3. Greetings ============== This program is based on the knowledged approach of L.Victor Allis which designed and implmented a sophisticated AI engine in a program called Victor. Velena is basically the same, except that even newer concepts and techinques were introduced in order to reduce the problem complexity (of solving the game) to a more tractable factor of magnitude. Moreover Velena is available to anyone, while Victor (currently) is not. I thank L.Victor Allis for his support while I developed Velena and for the theory he made for solving Connect Four. Without him this program wouldn't have come to light. I also thank Filippo Ghilardi who helped me to build the opening book data base which took several days of work on his Pentium 133 computer, and Davide Mazza who created the Velena intro logo. 2. Introduction into Connect Four ================================= Now I'll describe the rules of the game as well as some nomenclature used throughout this manual and some basic connect four strategy. 2.1. Game Rules =============== Connect Four is a two players game which takes place on a 7x6 rectangular board placed vertically between them. One player has 21 yellow men and the other 21 red men. Each player can drop a man at the top of the board in one of the seven columns; the man falls down and fills the lower unoccupied square. Of course a player cannot drop a man in a certain column if it's already full (i.e. it already contains six men). Even if there's no rule about which color should play first, in order to avoid confusion we will assume that men are either white or black (instead of yellow and red) and that white, as in chess, always plays first. Note however that Velena displays men in yellow and red even if here are refered as white and black respectively. Therefore when playing with Velena, yellow always begins first. The object of the game is to connect four men vertically, horizzontally or diagonally. If the board is filled and no one has alligned four men then the game is drawn (that is after 42 moves if no one wins). Here's an example of a game won by white (O) and black (X) in fig.1 and fig.2 respectively. A possible draw is represented in fig.3 ....... ....... OOOXOOO ....... ....... XXXOXXX ....... .XO.... OOOXOOO ...X... .XXO... XXXOXXX ...X... .OOX... OOOXOOO XOOOO.. .OXOX.. XXXOXXX Fig.1 Fig.2 Fig.3 White (O) wins Black (X) wins The Game is drawn 2.2. Nomenclature ================= Since we need a way for representing a sequence of moves instead of a position, I will use the same nomenclature as the one used for chess. This means that columns are named from A to G, starting from left, and rows are numbered from 1 to 6 starting from the bottom. In this way we could represent each square of the board with a pair letter-number. For example the square in the middle of the lowest row is d1. The square above is d2 and the square on the left of d1 is c1. (see fig. 3) 6 . . . . . . . 5 . . . . . . . 4 . . . . . . . 3 . . . . . . . 2 . . . . . . . 1 . . . . . . . A B C D E F G Fig. 3 In this way we could write down a game as a sequence of moves. For example the endgame of fig.1 could have arisen from the following sequence of moves: 1) d1,d2 2) c1,d3 3) b1,a1 4) e1++ where ++ indicates the player who did that move won the game (as in chess). 2.3. Game Strategy ================== There are two kinds of strategies in connect four. The first consist in looking ahead few moves to avoid the opponent to win and in the same time trying to connect four men. The other is looking for a win in the long run. Virtually all the alghoritms I have seen tend to implement the first strategy with some variants of alpha beta search and the most sophisticated ones with tree branch pruning. These strategies assure more or less the unvulnerability in the short run, but they are doomed to fail in the long run because they cannot see beyond the horizzon of few plies. Most of the games ends between 35th and 42nd move when you or the opponent is forced to make a particular move since there's only one column available. In this circumstance most of the people believe that the winner is lucky (if there's one). That's not it. An expert player is able to make this happen much time before. Actually this is what Velena does. The first step consist in noting that after white has moved an odd number of free squares remains on the board. Similary after black has moved an even number of free square remains. When there's only one column available it's clear that the last square will be occupied by black (if no one wins first). Now let introduce some definitions before continuing: ----------------------------------------------------------------------- ODD SQUARE: it's a square belonging to an odd row. For example d1,c1,c3, f5 are all odd squares. EVEN SQUARE: same as above except that the row is even. For example a2, b4,c6,e2 are all even squares. GROUP: it's a set of four squares connected horizzontally, vertically or diagonally. The first player who fills a group with his men, wins. THREAT: it's a group filled with three men of the same color which has the fourth square empty, and also the square below the empty square is empty. ODD THREAT: it's a therat in a group whose empty square is odd. EVEN THREAT: same as above but the empty square is even. DOUBLE THREAT: they are two groups which share an empty odd square; each group is filled with only two men (of the same color) and the other two squares (one for each group) are empty and are one above the other. The square below the shared square must be empty too. ----------------------------------------------------------------------- It's then clear that if white has an odd threat and black cannot connect four men anywhere, the game will be eventually won by white. Please note that this is a sufficient condition and if black can connect four men somewhere, further knowledge is required. Similary if black has an even threat and white cannot connect four men the game will be eventually won by black. It's clear that in both cases we assume that players make the best move available. Things get more complex when both players have at least one group in which they can connect four men. In this case we need further investigation. If white has an odd threat and black has an even threat and the columns in which the threats are (i.e. the empty square) are different then white can still win. Of course no player must be able to connect four men except in the group in which he has the odd/even threat stated above. But if columns are the same then the lower threat (i.e. the lower empty square) wins. If both players have an odd threat the game will be drawn. Unless one of them can connect four men elsewhere. Then the strategy for white is to try to obtain an odd threat and for black an even threat. This is not always sufficient as the restrictions above shows but it's a good starting point to play connect four, especially when both players are humans. 2.4. The Way Velena Plays ========================= When set to her strongest level, Velena uses two different strategies according she's playing white or black. In both cases she uses a database for the opening lines. The database is made in such a way that Velena is always able to reach a position in which she has an odd threat when she plays white (and from there she's able to continue and win by herself). She tries to follow the longest winning line for white when she plays with black. The built in evaluation function which examines the positions is then sufficient to play the middle and end game. However, further search is done just to check for trivial wins few moves ahed. 2.5. Drawbacks of the alghoritm =============================== Connect Four is not complex like chess. Therefore moves tends to repeat many times. For example the winning line for white is very narrow, so narrow that the first seven moves for white are forced. This is the reason why Velena is forced to answer almost always in the same way, given the same position on the board. There are not many variants. It's not strange that a player who keeps white men and learns how to win a game, is then always able to win each time he plays. This because he can play the same game each time. Another drawback is that Velena pays very poor attention to distinguish between a win for black and a draw. They are almost the same thing for her. Also note that Velena does the best move (when playing with white) only when she starts from the empty board. If someone sets up a position and then tells the computer to continue the game from that point, it's not warranted that the computer plays at best. Finally the algorithm tend to resign when a game is compromised and doesn't fight until the end. 3. Running Velena ================= After you have installed Velena on your hard disk, you can start the program simply typing "connect4" at the dos prompt. As already indicated in section 1.1, the program needs among the other things a SVGA VESA compatible card. Many cards can be made VESA compatible simply with a device driver that is in most of the cases provided with the graphic adapter itself. If you have any problem, look in your card manual. Besides there are also many freeware device drivers which can make your graphic adapter become VESA compatible. After a few seconds the computer will display the logo and then the board. Velena is ready to play. The program is entirely mouse driven and the commands are available as click-able gadgets in the top of the screen. 3.1. The Control Panel ====================== As you surely already noticed, Connect Four is very simple to understand and doesn't require too many operations to control the game options. The buttons in the top of the screen can drive the program with basic commands. Let's see their meaning: - New Game When you want to begin a new game, click this button and then confirm the option by answering YES. If you make a mistake or you change your mind you can answer NO and the command will be ignored. - Options When you want to set up a match between a player and the computer or two players, or an autoplay, click this button. You can also choose the computer level this way. By default red side is kept by Velena and yellow side (which begins first) is kept by the player. The default computer level is "strong". If you are unable to win (which is most likely), you can lower the level to "normal" or "weak". - Hint If you need a hint click this button and the computer will move for you. - Take Back This is probably the most used option. If you make a mistake and you want to undo the move made, just click this button. Note that when a two players game is set, only the last move is taken back. But when you play against the computer, moves are taken back two at time because you can take back only after the computer has made it's move. You can also take back more than one move by clicking repeatedly this button. - About Shows the program current version with other informations about the author and greetings. - Quit When you finished to play with Velena you can click this button and confirm you really want to quit. 3.2. Other commands =================== Moves are made by pointing the square in which the player in turn wants to play. You can also move with the keyboard by pressing keys 1..7, where 1 is the leftmost column and 7 the rightmost. F1 key can be used to flip colors on the screen (although men are always referenced as black and white). A file named CONNECT4.LOG is always updated on disk each time a game is over and keeps track of all the games played. 3.3. Advanced options ===================== With the right mouse button you can access a pull down menu with some advanced features. Here a brief description of what they mean: - Flash last move: It can be use to replay the last move made. The last man flashes for few seconds to let you understand for example where the computer moved. - Show moves list: Shows the moves so far in the chess notation described above. It also shows the moves in a column-wise manner which denotes only the column in which a player moved. - Position analysis Analyzes the current position on the board (for the side which is NOT in turn to move) and tells which is the theorical result that can be achieved if that player plays at best. Please note that only sufficient conditions are used for the analysis. This means that if the computer tells a game can be won, this is true, but if the computer says nothing this doesn't mean that a game can't be won. In other words it proceeds by sufficient conditions, not necessary. - Oracle analysis This is probably the most difficult feature to explain. It gives a detailed report of the oracle status (which is one of the three engines which drive Velena, and besides the most important one). Since rules definitions and applications are difficult to understand, I suggest you to refer to L.V.Allis thesis "A knowlede based approach of Connect Four" to know more. Once you red and understood that thesis you'll be able to understand the report Velena gives with this option. Refer to paragraph 4.8 for further informations. Please note that also the oracle proceeds by sufficient conditions; there are some positions where the game result is clear and the oracle seems not to foresee it. - Reset counters Resets the two counters which keep players score (shown at the top of the board). - Change colors It simply changes the palette, swapping the three main colors components. This leads to a total of six different combinations. - Save moves list Writes to disk an ascii file with the moves made. The file name is choosen automatically. - Save screen to disk Writes an image in GIF format with the current position on the board. The GIF can be in two colors or in 256 colors according to your needs. The 256 color GIF is the current Velena screen, while the 2 colors screen is simply a diagram which is pretty useful if you want to print it. 4. Why Velena is so special =========================== As already said before, Velena is an expert system able to play the game perfectly. This means that if the program is set to it's maximum level of strength she always wins when she plays first and she is almost impossible to beat when she plays second (until you make a few games and you will learn how to beat her by the program herself). Of course if you are a beginner you can set a lower difficulty level for the computer. This is useful if you are interested in learning how to play. 4.1. Game complexity ==================== Although at first sight Connect Four doesn't seem a very complex game in terms of combinations of moves and the number of reachable different positions on the board, it should be noticed that it's not so a trivial game as it looks. Let's see some mathematics behind it. First we can make a raw estimation of game complexity noting that since each square can be empty or occupied by either white or black, each square can be in only three different states, leading a total game complexity of 3^42 which is in the order of 10^20. Of course this is an upper bound which takes in count also the illegal positions. It is possible to make some finer estimations that reduces the number of legal positions, anyway even the finest estimation gives us an order of magnitude of 7.1 x 10^13, which is still to high for a complete enumeration. To build up a brute force attack several terabytes of disk space would be required, and current technology is far away from this possibility. Besides the space requirements, also the time requirements would be out of what are called "reasonable resources". Finally it would be almost impossible to distribute the program. 4.2. So Velena is not a brute force attack against Connect Four? ================================================================ Definitly not. Velena is an intelligent program which is able to predict the final result of a game using complex mathematics, and efficient search strategies. The program is compact and strong; only a tiny opening book of about 60.000 positions is used for the opening lines. All the rest is calculated on fly. 4.3. So why should I use Velena if it's unbeatible? =================================================== Well, there are several reasons why this program can be useful. First it represents the final word on Connect 4 (or so I hope): no program or living man can outperform Velena. Besides, Velena is very useful to train yourself against a human player. If you want to become a strong player then you should train yourself with a strong player. And Velena is the strongest. 4.4. But is Velena really so perfect? ===================================== Well, it's perfect in the sense that she's always able to win if she plays first. This because it can be mathematically shown that Connect Four can be won by the player which plays first (if it plays well) no matter how good the opponent is. Of course if Velena plays second, there's still a chance for the human player to defeat her. Once you learned how, you can easiliy win. More over the purpose of the computer in this case (when playing second) is not to win, but to avoid losing, if possible. In other words Velena considers a draw a good result if it plays with red men. 4.5. So Velena destroyed Connect Four? ====================================== Yes, but humans are humans and machines are machines. Connect Four is still interesting if played between two men. Of course there are no chances between a man and a computer, like there are no chances between a man and a car. The latter will run always faster. 4.6. Why does Velena play almost always the same game when she's in autoplay? ================================================================= Connect four is not like chess. Even if the game is not as trivial as tic tac toe, the complexity is much smaller than chess. This of course leads to a limited number of variants and often the moves are forced. For example there's only one winning way for white and the first seven moves are forced for him. If he choses another move, black can draw. Similary black has only one strong defensive line (which of course falls in the long run) which can protect him from a premature loss. It's clear that once you learn how to infiltrate in this line, you are likely to win each time against black. 4.7. Isn't Velena too slow in replying? ======================================= It depends on which machine she runs. Theorically it can run on a 386 based processor, but she surely will take a lot of time. At least a 486DX2 is required to play at decent speed. Anyway the algorithm behind is very complex, and no time is wasted in useless delays. Velena needs all the resources she uses. Believe me! 4.8. Where can I find the complete description of the algorithms used here? =========================================================================== You can try: ftp://ftp.cs.vu.nl/~victor/connect4.zip ftp://ftp.cs.vu.nl/~victor/thesis.zip this is the documentation made available by L.Victor Allis and surely it's very interesting. Of course I am not sure that it will be there forever. Please contact victor@cs.vu.nl for more informations. Keep also in mind that this program is based on his theory but it does not follow it completely. For example the mathematical rules have been reduced from nine to eight. You can also refer to Velena Home Page at: http://www.ce.unipr.it/~gbe/velena.html 4.9. Where can I get the last version of Velena =============================================== Check out Velena's Home Page at: http://www.ce.unipr.it/~gbe/velena.html or use a net serach engine. 4.10. Is the source code of Velena available to the public? =========================================================== No, at the moment it's not. Maybe one day it will. 4.11. Who's F.Alinovi and why did he say: "...who wants to make four?" ====================================================================== He's a friend. After I bored him telling the inner workings of Velena and the clever idea behind the algorithm he answered that way. He also added that I was losing my time. Poor little fellow! :)))) 4.12. What's "a Shannon-C type program" mean? In his famous paper in 1950 C.Shannon describes three methods by which a machine could play a strategy game (such chess, checkers, connect four and so on...). The C-type method consist in emulating human mind to take decisions. In other words the eight mathematical rules Velena uses are not based on a search algorithm but on the properties of the game. The A-type method instead is based on pure brute force search. Just to be fair Velena is not only a Shannon-C type program since it also uses some search algoritms to play, anyway the great difference in playing capabilities relies just on this knowledged approach, which made possible to solve the game. =============================================================================== Further details will be given if requested. Please write in english or in italian. =============================================================================== The author: Giuliano Bertoletti Via Bocchialini n.6 Cap. 43100 Parma gbe@aida.eng.unipr.it